/**
 * 198. House Robber 打家劫舍
 * https://leetcode-cn.com/problems/house-robber/
 */
class HouseRobber {

    /**
     *      方法： 使用动态规划求解打家劫舍问题
     *            f[i]表示偷窃前i个房屋能获得的最大金额
     *            状态转移方程：f[i] = max(f[i-1], f[i-2] + nums[i])
     *            使用滚动数组优化空间复杂度
     *
     *      Args:
     *          nums: List[int] - 每个房屋存放的金额列表
     *
     *      Returns:
     *          int: 在不触动警报装置的情况下能够偷窃到的最高金额
     *
     *      Time: O(n) - 其中n是房屋数量，需要遍历一次数组
     *
     *      Space: O(1) - 只使用了两个变量来存储状态，空间复杂度是常数级别
     */
    public int rob(int[] nums) {
        int f0 = 0, f1 = 0;
        for(int i = 0; i< nums.length; i++){
            int newF = Math.max(f1, f0 + nums[i]);
            f0 = f1;
            f1 = newF;
        }
        return f1;
    }
}